The present invention pertains to volume graphics and more specifically, to a technique for graphically modeling the cutting of volumetric objects along an arbitrary cutting path, the joining together of volumetric objects of arbitrary shape at an arbitrary surface, and the tearing of deformable volumetric object models when they are pulled apart.
Computer based simulation has many applications. One such application involves surgical simulation. Computer based surgical simulation has application in surgical training, education, surgical planning and with intra-operative assistance. In medical education and training, surgical simulation can reduce costs associated with cadaver specimens, provide experience with a greater variety of pathologies and complications that would normally be encountered in practice, and provide the ability to repeat or replay training procedures. In surgical planning, simulators enable rehearsal of difficult procedures or planning of surgeries involving patient specific anatomies. Intra-operatively, computer modeling can aid in navigation by augmenting the limited surgical field with a more global view of the patient's anatomy and may provide guidance, for example, by warning the prospective surgeon with respect to intrusion into regions where harm could be caused to the patient.
In order to provide useful feedback to the user, surgical simulators must provide adequate realism. Tissue models should respond in a realistic way when they are manipulated. Rendered images of the surgical field must be realistic enough to be compelling. Haptic or force feedback must mimic forces experienced in real life because the sense of touch provides important cues in surgery. These requirements impose significant demands on the surgical simulator and more particularly, they require physically realistic modeling techniques which simulate soft tissue deformation, tissue cutting, tearing or joining.
In computer modeling, digital models of physical objects are manipulated to simulate or predict real-world behavior. In physics-based graphics, physical laws are used to model interactions such as collisions between object models or the deformation of soft objects. Physically-plausible implies that the physical modeling has the appearance of being realistic even though it may not be strictly accurate. Physically-plausible simulations can be much less computationally intensive than physically-realistic simulations but they are often sufficient in applications such as character animation, high-level design or education.
In surface-based graphics, graphical objects are represented by a set of contiguous surface elements such as polygons or curved spline patches. Modeling of cutting through surface-based objects is difficult because new contiguous surfaces must be constructed along the cutting path. If the cut can be made through arbitrary positions in the model, construction of cutting plane surfaces can be quite difficult. In addition, because object interiors are not represented in surface models, interior structure at the cut must be fabricated over the cutting surface so that the cut looks realistic.
In volume graphics, objects are represented as three dimensional arrays of sampled data elements. Volumetric models represent both object surfaces and object interiors. Because object interiors are represented, it is possible to model volumetric deformations (see "3D ChainMail, a fast algorithm for deforming volumetric objects", by S. Gibson, in Proc. CVRMed/MRCAS 97, pp. 369-378, Grenoble, Fr. 1997) and to use the internal detail both for influencing the cut path (for example if the cut path encounters a dense structure inside the object) and for modifying the appearance of the surface exposed by the cut.
Sculpting of volumetric objects has been performed by others such as: Galyean and Hughes in "Sculpting: An interactive volumetric modeling technique", Proc. SIGGRAPH 91, Las Vegas, Nev., pp. 267-274, July, 1991; S. Wang and A. Kaufman in "Volume Sculpting, Proc. 1995 Symp. on Interactive 3D Graphics", Monterey, Calif., pp. 151-156, May, 1995; and R. Avila and L. Sobierajski in "A haptic interaction method for volume visualization", Proc. IEEE Visualization 96, pp. 197-204, San Francisco, Calif., October, 1996. In these methods, objects are represented by a static array of regularly spaced intensity values, where the sample intensities correspond to tissue density or the amount of material at that sample point. (For example, a density of 1 might correspond to solid material or a "full" sample, and a density of 0 might corresponds to empty space.) Sculpting or editing of the volume is performed by changing the sample density values near the sculpting tool. For example, "carving" sets to zero density values in elements of the array that are underneath the tool, "melting" reduces the density of voxels underneath the tool proportionally with the time that the tool is over an array element, and "spraying" adds material by increasing the density of voxels underneath the tool up to the maximum density of 1.
While these volumetric sculpting techniques have potential applications in volume editing and geometric design, it is important to note that the resultant array of intensity values lacks the physical sense of being an object. Once pieces in the array are "carved" away from the rest of the volume, they cannot be manipulated as individual objects. Material is created and dissolved into thin air, so that these applications do not realistically model real sculpting. In addition, it is not clear how this representation could be extended for sculpting deformable materials.
Finite element methods can be used to model deformable objects. Like volumetric methods, finite element methods use a three dimensional mesh of node points. The dynamics of these systems can be predicted by solving large systems of simultaneous ordinary differential equations with dimensionality proportional to the number of nodes in the discrete model. Finite element methods give physically realistic behavior, however, they are computationally intensive. Additionally, arbitrary cutting through the three dimensional mesh requires remeshing of the model. This remeshing is required for accurate simulations because smaller meshes are required at high stress points (for example the tip of the knife).
Terzopoulos and Fleischer model fracturing of a discrete mesh representation of deformable tissues in "Modeling inelastic deformation: viscoelasticity, plasticity, fracture", Proc. SIGGRAPH 88, Computer Graphics, Vol. 22, pp. 269-278, 1988. However, in their model, fracturing results from zeroing material property weighting functions at particular mesh nodes rather than an explicit removal of a connection between two linked elements as in the subject invention.
Modeling, cutting or tearing of three dimensional objects is difficult with surface-based representations because new surfaces must be constructed along the arbitrary knife path. In addition, because surface-based models do not represent object interiors, cutting or tearing through these models requires fabricating the interior structure to provide color or texture for the cut surface.
Current volumetric sculpting methods assume that the object is a static three dimensional array of density values. These density values are increased or decreased to represent addition or removal of material but there is no way to physically simulate the actions of cutting, tearing, or joining. Objects that are created, cut apart, or joined have no physical properties that can be used for physics-based modeling